package leetcode.solution;

import java.util.*;

/**
 * 作为项目经理，你规划了一份需求的技能清单 req_skills，并打算从备选人员名单 people 中选出些人组成一个「必要团队」（ 编号为 i 的备选人员 people[i] 含有一份该备选人员掌握的技能列表）。
 *
 * 所谓「必要团队」，就是在这个团队中，对于所需求的技能列表 req_skills 中列出的每项技能，团队中至少有一名成员已经掌握。
 *
 * 我们可以用每个人的编号来表示团队中的成员：例如，团队 team = [0, 1, 3] 表示掌握技能分别为 people[0]，people[1]，和 people[3] 的备选人员。
 *
 * 请你返回 任一 规模最小的必要团队，团队成员用人员编号表示。你可以按任意顺序返回答案，本题保证答案存在。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
 * 输出：[0,2]
 * 示例 2：
 *
 * 输入：req_skills = ["algorithms","math","java","reactjs","csharp","aws"], people = [["algorithms","math","java"],["algorithms","math","reactjs"],["java","csharp","aws"],["reactjs","csharp"],["csharp","math"],["aws","java"]]
 * 输出：[1,2]
 *  
 *
 * 提示：
 *
 * 1 <= req_skills.length <= 16
 * 1 <= people.length <= 60
 * 1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16
 * req_skills 和 people[i] 中的元素分别各不相同
 * req_skills[i][j], people[i][j][k] 都由小写英文字母组成
 * 本题保证「必要团队」一定存在
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/smallest-sufficient-team
 */
public class 最小的必要团队 {

    /**
     * 有问题 复杂度过高
     */
    static class Solution {
        public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
            HashMap<String, Integer> m = new HashMap<>();
            int j = 0;
            for (String i : req_skills){
                m.put(i,j);
                j++;
            }
            int peopleNum = people.size();
            int skillNum = j;
            // 将人员技能用二进制表示 (因为技能不超过16个）
            int[] peopleSkills = new int[peopleNum];
            j = 0;
            for (List<String> i : people){
                int tmp = 0;
                for (String z : i){
                    tmp += (1 << m.get(z));
                }
                peopleSkills[j] = tmp;
                j++;
            }
            // 技能全集
            int[] skills = new int[skillNum];
            j = 0;
            for (String i : req_skills){
                skills[j] = 1 << m.get(i);
                j++;
            }
            int target = target(skills);
            // 声明dp
            int[] dp = peopleSkills.clone();
            LinkedList<List<int[]>> dpList = new LinkedList<>();
            List<int[]> tt = new ArrayList<>();
            tt.add(dp);
            dpList.push(tt);
            int[] res = dp.clone();
            while (!dpList.isEmpty()){
                List<int[]> curr = new ArrayList<>();
                for (int[] tmp : dpList.poll()){
                    res = tmp;
                    for (int i = 0; i < tmp.length; i++){
                        if (tmp[i] != 0){
                            int z = tmp[i];
                            tmp[i] = 0;
                            if (target == target(tmp) && !isSame(tmp, curr)){
                                curr.add(tmp.clone());
                            }
                            tmp[i] = z;
                        }
                    }
                }
                if (!curr.isEmpty()) dpList.push(curr);
            }
            List<Integer> a = new ArrayList<>();
            for (int i = 0; i < res.length; i++){
                if (res[i] != 0){
                    a.add(i);
                }
            }
            int[] r = new int[a.size()];
            for (int i = 0; i < r.length; i++){
                r[i] = a.get(i);
            }
            return r;
        }

        private static int target(int[] a){
            int res = 0;
            for (int i : a){
                res = (res+i)-(res&i);
            }
            return res;
        }

        private static boolean isSame(int[] a , List<int[]> b){
            for (int[] i : b){
                if (Arrays.equals(a,i)) return true;
            }
            return false;
        }

    }

    /**
     *
     * 通过 已有技能的二进制和 作为dp的下标, dp记录所需人数 -》 达到某种技能组合所需人数
     *
     * 本题属于典型的0-1背包问题了，额外增加的就是预处理的过程：将状态进行压缩。稍微复杂一点的就是求所选的物品，这里我们可以采用记录前一个状态(preState)和两个状态转换用到的物品(pre), 然后从后往前遍历结果就可以了
     *
     * 作者：HenryLee4
     * 链接：https://leetcode-cn.com/problems/smallest-sufficient-team/solution/0-1bei-bao-wen-ti-java-by-henrylee4/
     * 来源：力扣（LeetCode）
     */
    static class Solution1 {
        public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
            // n 技能数 m 人数
            int n = req_skills.length, m = people.size();
            Map<String, Integer> map = new HashMap<>();
            for(int i = 0 ; i < n ; i++){
                map.put(req_skills[i], i);
            }
            // 存储每个人 技能的二进制数
            int[] mask = new int[m];
            for(int i = 0 ; i < m; i++){
                mask[i] = convert(people.get(i), map);
            }
            // dp[i]表示满足一定技能条件所需的人数 i表示技能的二进制表示 由于技能用二进制表示 所以最大是 n * 2 即 技能数×2
            int[] dp = new int[1 << n];
            Arrays.fill(dp, -1);
            // 初始状态 0 技能 0人
            dp[0] = 0;
            // 记录前置条件
            int[] preState = new int[1 << n];
            // 记录人员编号
            int[] pre = new int[1 << n];
            for(int i = 0; i < m ; i++){
                for(int j = (1 << n) - 1; j >= 0; j--){
                    // 不存在
                    if(dp[j] == -1){
                        continue;
                    }
                    // 在条件j 的情况下 添加人员i 条件变更为state
                    int state = j | mask[i];
                    if(dp[state] == -1 || dp[state] > dp[j] + 1){
                        // 新的条件未到达到过或所需人数大于添加i 则更新
                        dp[state] = dp[j] + 1;
                        // 记录前置条件 以方便回溯人员编号
                        preState[state] = j;
                        // 记录人员编号
                        pre[state] = i;
                    }
                }
            }
            List<Integer> res = new ArrayList<>();
            int state = (1 << n) - 1;
            while(state != 0){
                res.add(pre[state]);
                state = preState[state];
            }
            int[] array = new int[res.size()];
            for(int i = 0 ; i < res.size() ; i++){
                array[i] = res.get(i);
            }
            return array;
        }

        private int convert(List<String> list, Map<String, Integer> map){
            int res = 0;
            for(String s: list){
                if(map.containsKey(s)){
                    res |= 1 << map.get(s);
                }
            }
            return res;
        }
    }

    public static void main(String[] args){
        String[] a = new String[]{"algorithms","math","java","reactjs","csharp","aws"};
        List<String> b1 = Arrays.asList(new String[]{"algorithms","math","java"});
        List<String> b2 = Arrays.asList(new String[]{"algorithms","math","reactjs"});
        List<String> b3 = Arrays.asList(new String[]{"java","csharp","aws"});
        // ["reactjs","csharp"],["csharp","math"],["aws","java"]
        List<String> b4 = Arrays.asList(new String[]{"reactjs","csharp"});
        List<String> b5 = Arrays.asList(new String[]{"csharp","math"});
        List<String> b6 = Arrays.asList(new String[]{"aws","java"});
        List<List<String>> b = new ArrayList<>();
        b.add(b1);
        b.add(b2);
        b.add(b3);
        b.add(b4);
        b.add(b5);
        b.add(b6);
        for (int i : new Solution1().smallestSufficientTeam(a,b)){
            System.out.println(i);
        }
        System.out.println();
    }
}
